#include "stack_queue.h"
#include <iostream>
using namespace std;
//先实现节点的函数
listNode::listNode(int nodeData, listNode *succ) 
{
    data = nodeData;
    next = succ;
}

listNode::listNode() 
{
    next = nullptr;
    data=0;
}

void MyStack::printStack() //输出栈内元素
{
    listNode* p = topNode;

    while(p != NULL)
    {
        if(p->next == NULL)
        {
            cout << p->data << endl;
        }
        else
        {
            cout << p->data << ",";
        }
        p = p->next;
    }
}

MyStack::MyStack()
{
    topNode = nullptr;
    stackSize=0;
}

MyStack::~MyStack() //栈销毁
{
    while(topNode!=nullptr)//当栈不为空
    {
        listNode* p = topNode;
        topNode =topNode->next;
        delete p;
    }
}

bool MyStack::push(const int& yuansu)//入栈
{
    listNode* ding = new listNode(yuansu);
    if(ding == nullptr)
    {
        return false;
    }
    ding ->next = topNode;
    topNode = ding;
    stackSize++;
    return true;
}

bool MyStack::pop(int& yuansu) //出栈
{

    if(topNode == nullptr)  //栈空
    {
        return false;
    }
    
    yuansu =topNode ->data;
    listNode* p = topNode;
    topNode =topNode ->next;
    delete p;
    
    stackSize--;
    return true;
}

bool MyStack::getTop(int& yuansu) //取栈顶元素
{
    if(topNode == nullptr)  //栈空
    {
        return false;
    }
    yuansu =topNode ->data;
    return true;
}


bool MyStack::isEmpty() const   // 检查栈是否为空
{
    return topNode == nullptr;
}



void MyQueue::printQueue() //输出队列内元素
{
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)//已经输出到最后一个元素
        {
            cout << queue[cursor] << endl;
        }
        else
        {
            cout << queue[cursor] << ",";
        }
        cursor = (cursor + 1) % capacity;
    }
}

MyQueue::MyQueue(const int& daxiao): capacity(daxiao),front(0),rear(0)//初始化队列
{
    queue = new int[capacity];
}

MyQueue::~MyQueue() //销毁队列
{
    delete[] queue;
}

bool MyQueue::enQueue(const int& yuansu) //入队
{
    if(isFull())//队满
    {
        return false;
    }
    queue[rear]=yuansu;
    rear=(rear+1)%capacity;
    return true;
}

bool MyQueue::deQueue(int& yuansu) //出队
{
    if(rear==front) //队空
    {
        return false;
    }
    yuansu =queue[front];
    front=(front+1)%capacity;
    return true;
}

bool MyQueue::getFront(int& yuansu) //返回队头元素
{
    if(rear==front) //队空
    {
        return false;
    }
    yuansu =queue[front];
    return true;
}

bool MyQueue::isFull()
{
    if((rear+1)%capacity==front)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//队列不插满，留一个空，若是插满，则按上法构造的循环队列对于队列满和队列空无法区别 
  
void yanghui(const int& n)  //杨辉三角
{  
    MyQueue q(n + 3);  
    //队列初始化
    //通过观察可以发现第一行需要三个位置，
    //第二行需要四个位置，
    //以此类推，第n行需要n+2个位置（n+1个数据，1个辅助运算的0）
    //又因为队列不插满，需要留出一个位置，所以n+3

    q.enQueue(1);  
    q.enQueue(1);
    int s=0;
    //逐行处理，输出第一行参数的同时计算第二行参数并入栈
    //（0） 1 1 0
    for (int i = 1; i <=n; ++i)  
    {  
        q.enQueue(0); 
  
        for (int j = 1; j <=i+2; ++j)  
        {  
            int t;
            q.deQueue(t);
            q.enQueue(s+t);
            s=t;
            if(j!=i+2)
            {
                if(j!=i+1)
                {
                    cout<<s<<",";//非本行最后一个输出数时，后面带一个逗号
                }
                else
                {
                    cout<<s;
                }
            }
        } 
        cout<<endl;  
    }  
}


int precedence(char op) // 运算符优先级
{
    switch (op) 
    {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}
  


bool postfixExpression(const string& expression, string& result)// 中缀表达式转换为后缀表达式
{
    MyStack operatorStack;
    result.clear();
    
    for (char c : expression) 
    {
        if (isdigit(c)) // 是数字
        { 
            result += c;  // 添加到后缀表达式中
        } 
        
        else if (c == '(') //左括号
        { 
            operatorStack.push(c);//入栈
        } 
        
        else if (c == ')') // 右括号
        { 
            int topOperand;
            while (operatorStack.getTop(topOperand) && topOperand != '(') //栈非空且不为左括号，持续弹出
            {
                result += static_cast<char>(topOperand); // 弹出并添加到结果
                operatorStack.pop(topOperand);
            }
            if (!operatorStack.getTop(topOperand)) // 没有对应的左括号
            { 
                result = "Expression is wrong!";
                return false;
            }
            operatorStack.pop(topOperand); // 弹出左括号
        } 
        
        else if (precedence(c) > 0) //是运算符
        { 
            while (!operatorStack.isEmpty()) //栈非空
            {
                int topOp;
                operatorStack.getTop(topOp); // 获取栈顶运算符
                if (precedence(static_cast<char>(topOp)) >= precedence(c)) //栈顶运算符的优先级大于当前扫描到的运算符的优先级
                {
                    operatorStack.pop(topOp);
                    result += static_cast<char>(topOp); // 弹出栈顶运算符并添加到结果
                } 
                else 
                {
                    break; // 优先级低的话退出循环
                }
            }
            operatorStack.push(c); // 无论如何当前运算符都是要入栈的，区别只是之前的栈顶运算符是否要出栈
        } 
        
        else // 无效字符
        {
            result = "Expression is wrong!";
            return false; 
        }
    }

    
    while (!operatorStack.isEmpty()) // 处理完输入后，将栈中所有运算符弹出
    {
        int topOp;
        operatorStack.pop(topOp);
        if (topOp == '(')  // 不匹配的括号
        {
            result = "Expression is wrong!";
            return false;
        }
        result += static_cast<char>(topOp);
    }

    return true;
}


bool expressionVal(const string& expression, int& result) // 表达式求值
{
    string postfix;
    if (!postfixExpression(expression, postfix)) //所给的表达式不能转化为后缀表达式
    {
        result = 0;
        return false;
    }

    MyStack evalStack;
    for (char c : postfix) 
    {
        if (isdigit(c)) 
        {
            evalStack.push(c - '0'); //数字入栈
        } 
        else // 运算符
        { 
            int rightOperand, leftOperand;
            evalStack.pop(rightOperand);
            evalStack.pop(leftOperand);//弹出两个数
            int res = 0; //储存两个数的运算结果

            switch (c) 
            {
                case '+': res = leftOperand + rightOperand; break;
                case '-': res = leftOperand - rightOperand; break;
                case '*': res = leftOperand * rightOperand; break;
                case '/':
                    if (rightOperand == 0) // 除以零
                    {
                        result = 0;
                        return false; 
                    }
                    res = leftOperand / rightOperand; 
                    break;
                
                default:
                    result = 0;
                    return false; 
                    
            }
            evalStack.push(res); // 将结果放入栈中
        }
    }

    if (!evalStack.getTop(result)) //无法取出运算结果
    { 
        result = 0;
        return false; 
    }
    return true;
}